package collection;

import exception.CollectionEmptyException;

public class DLinkedList<T> extends ALinkedList<DNode<T>, T>{
	
	public DLinkedList()
	{
		super();
	}
	
	public DLinkedList(DLinkedList<T> other)
	{
		super(other);
	}
	
	@Override
	protected DNode<T> createHead() 
	{
		return new DNode<T>();
	}
	
	@Override
	public DNode<T> createNode(T element) 
	{
		return new DNode<T>(element);
	}
	
	@Override
	public void addFirst(DNode<T> newNode)
	{
		if (isEmpty())
		{
			//since head==tail, it should be the same as addToTail(newNode)
			addLast(newNode);
		}
		else
		{
			DNode<T> oldNode = super.head.getNext();
			oldNode.setPrev(newNode);
			newNode.setNext(oldNode);
			newNode.setPrev(super.head);
			super.head.setNext(newNode);
			super.size += 1;
		}
	}
	
	@Override
	public void addLast(DNode<T> newNode)
	{
		newNode.setNext(null);
		newNode.setPrev(super.tail);
		super.tail.setNext(newNode);
		super.tail = newNode;
		super.size += 1;
	}
	
	@Override
	public DNode<T> removeFirst()
	{
		if (isEmpty())
		{
			throw new CollectionEmptyException("Linked List");
		}
		
		// get the first node
		DNode<T> firstNode = super.head.getNext();
		
		// there is only one element
		if (firstNode.getNext() == null)
		{
			super.head.setNext(null);
			super.tail = super.head;
		}
		else // there are more than one elements
		{
			DNode<T> secondNode = firstNode.getNext();
			secondNode.setPrev(super.head);
			super.head.setNext(secondNode);
		}
		
		super.size -= 1;
		
		return firstNode;
	}
	
	@Override
	public DNode<T> removeLast()
	{
		if (isEmpty())
		{
			throw new CollectionEmptyException("Linked List");
		}
		
		// get the last node
		DNode<T> lastNode = super.tail;
		
		// there is only one element
		if (super.head.getNext() == lastNode)
		{
			super.head.setNext(null);
			super.tail = super.head;
		}
		else // there are more than one elements
		{
			//find the node before the last node
			DNode<T> secondToLastNode = lastNode.getPrev();
			secondToLastNode.setNext(null);
			super.tail = secondToLastNode;
		}
		
		super.size -= 1;
		
		return lastNode;
	}
	
	@Override
	public void reverse()
	{
		if (size()<=1)
		{
			return ;
		}
		
		DNode<T> headNode  = super.head;
		DNode<T> firstNode = headNode.getNext();
		DNode<T> lastNode  = super.tail;
		
		DNode<T> curNode = firstNode;
		while(curNode.getNext() != null)
		{
			DNode<T> prevNode = curNode.getPrev();
			DNode<T> nextNode = curNode.getNext();
			curNode.setPrev(nextNode);
			curNode.setNext(prevNode);
			curNode = nextNode;
		}
		firstNode.setNext(null);
		lastNode.setNext(lastNode.getPrev());
		lastNode.setPrev(headNode);
		headNode.setNext(lastNode);
		super.tail = firstNode;
	}
	
	@Override
	public void remove(DNode<T> someNode)
	{
		if (isEmpty())
		{
			return ;
		}
		
		DNode<T> firstNode = super.head.getNext();
		if (firstNode == someNode)
		{
			removeFirst();
			return ;
		}
		if (super.tail == someNode)
		{
			removeLast();
			return ;
		}
		
		DNode<T> curNode = firstNode;
		while(curNode != null)
		{
			if (curNode == someNode)
			{
				DNode<T> prevNode = curNode.getPrev();
				DNode<T> nextNode = curNode.getNext();
				if (prevNode != null)
				{
					prevNode.setNext(nextNode);
				}
				if (nextNode != null)
				{
					nextNode.setPrev(prevNode);
				}
				
				super.size -= 1;
				
				return ;
			}
			curNode = curNode.getNext();
		}
	}

	@Override
	public DNode<T> getPrev(DNode<T> someNode) 
	{	
		return (someNode.getPrev() == super.head? null : someNode.getPrev());
	}

	@Override
	public DNode<T> getNext(DNode<T> someNode) 
	{	
		return someNode.getNext();
	}

	@Override
	public void addBefore(DNode<T> someNode, DNode<T> newNode) 
	{	
		if (super.head.getNext() == someNode)
		{
			addFirst(newNode);
			return ;
		}
		
		DNode<T> prevNode = getPrev(someNode);
		prevNode.setNext(newNode);
		newNode.setPrev(prevNode);
		someNode.setPrev(newNode);
		newNode.setNext(someNode);
		super.size += 1;
	}

	@Override
	public void addAfter(DNode<T> someNode, DNode<T> newNode) 
	{
		if (super.tail == someNode)
		{
			addLast(newNode);
			return ;
		}
		
		DNode<T> nextNode = getNext(someNode);
		someNode.setNext(newNode);
		newNode.setPrev(someNode);
		newNode.setNext(nextNode);
		if (nextNode != null)
		{
			nextNode.setPrev(newNode);
		}

		super.size += 1;
	}

}

